package leetcode.binaryTree;

import utils.printer.BinaryTrees;
import datastructure.tree.BinarySearchTree;
import datastructure.tree.TreeNode;

/**
 * @Description: https://leetcode.cn/problems/invert-binary-tree/
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 * 将所有叶子节点的的左右子树值交换
 * @Author Ammar
 * @Create 2023/3/28 21:12
 */
public class _226_翻转二叉树 {

    /**
     * 思路，将所有叶子节点的左右子树交换
     * 前序遍历节点
     *
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        // 将节点的左右交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    public static void main(String[] args) {
        Integer[] data = new Integer[]{
//                7, 4, 9, 2, 5, 8 ,11, 3, 12, 1
                9, 7, 12, 5, 8, 11, 13, 3
        };
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            binarySearchTree.add(data[i]);
        }

        BinaryTrees.print(binarySearchTree);
        invertTree(binarySearchTree.getRoot());
        BinaryTrees.print(binarySearchTree);
    }
}
